{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Mirror Reflection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mirrorReflection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #镜面反射"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为&nbsp;<code>0</code>，&nbsp;<code>1</code>，以及&nbsp;<code>2</code>。</p>\n",
    "\n",
    "<p>正方形房间的墙壁长度为&nbsp;<code>p</code>，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 <code>0</code> 的距离为 <code>q</code> 。</p>\n",
    "\n",
    "<p>返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/18/reflection.png\" style=\"width: 218px; height: 217px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>p = 2, q = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>p = 3, q = 1\n",
    "<strong>输入：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= q &lt;= p &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [mirror-reflection](https://leetcode.cn/problems/mirror-reflection/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [mirror-reflection](https://leetcode.cn/problems/mirror-reflection/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n1', '3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        while q & 1 == 0 and p & 1 == 0:\n",
    "            q >>= 1\n",
    "            p >>= 1\n",
    "        if p & 1 == 0:\n",
    "            return 2\n",
    "        if q & 1 == 0:\n",
    "            return 0\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(p, q):\n",
    "            if p < q:\n",
    "                p, q = q, p\n",
    "            while p % q != 0:\n",
    "                p, q = q, p % q\n",
    "            return q\n",
    "        lcm = (p * q) // gcd(p, q)\n",
    "        x, y = lcm // q, lcm // p\n",
    "        if x % 2 == 1 and y % 2 == 0:\n",
    "            return 0\n",
    "        elif x % 2 == 1 and y % 2 == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        return (lambda x:q//x&1 if p//x&1 else 2)(math.gcd(q,p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        lcm = math.lcm(p, q)\n",
    "        x = lcm / p\n",
    "        y = lcm / q\n",
    "        if x % 2 == 0:\n",
    "            return 0\n",
    "        elif y % 2 == 0:\n",
    "            return 2\n",
    "        else:\n",
    "            return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def mirrorReflection(self, p, q):\n",
    "        from fractions import Fraction as F\n",
    "\n",
    "        x = y = 0\n",
    "        rx, ry = p, q\n",
    "        targets = [(p, 0), (p, p), (0, p)]\n",
    "\n",
    "        while (x, y) not in targets:\n",
    "            #Want smallest t so that some x + rx, y + ry is 0 or p\n",
    "            #x + rxt = 0, then t = -x/rx etc.\n",
    "            t = float('inf')\n",
    "            for v in [F(-x,rx), F(-y,ry), F(p-x,rx), F(p-y,ry)]:\n",
    "                if v > 0: t = min(t, v)\n",
    "\n",
    "            x += rx * t\n",
    "            y += ry * t\n",
    "\n",
    "            #update rx, ry\n",
    "            if x == p or x == 0: # bounced from east/west wall, so reflect on y axis\n",
    "                rx *= -1\n",
    "            if y == p or y == 0:\n",
    "                ry *= -1\n",
    "\n",
    "        return 1 if x==y==p else 0 if x==p else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        x = gcd(p, q)\n",
    "        p, q = p // x, q // x\n",
    "        if p % 2:\n",
    "            if q % 2:return 1\n",
    "            return 0\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        if q == p: return 1\n",
    "        x = q\n",
    "        while True:\n",
    "            x += q\n",
    "            if x % (2*p) == p: return 2\n",
    "            x += q\n",
    "            if x % (2*p) == p: return 1\n",
    "            if x % (2*p) == 0: return 0\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        p_q_lcm = self.lcm(p, q)\n",
    "        ref_p = p_q_lcm // p\n",
    "        ref_q = p_q_lcm // q\n",
    "        if ref_p % 2 == 0:\n",
    "            return 0\n",
    "        if ref_q % 2 == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2\n",
    "\n",
    "    def lcm(self, a, b):\n",
    "        return a * b // math.gcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(p, q):\n",
    "            while q != 0:\n",
    "                p, q = q, p % q\n",
    "            return p\n",
    "        gbs = p * q // gcd(p,q)\n",
    "\n",
    "        if (gbs // p) % 2 == 0:\n",
    "            return 0\n",
    "        if (gbs // q) % 2 == 1:\n",
    "            return 1\n",
    "        if (gbs // q) % 2 == 0:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        n = 1\n",
    "        while n * q % p:\n",
    "            n += 1\n",
    "        \n",
    "        if (n * q // p) % 2:\n",
    "            if n % 2:\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        m = lcm(p, q)\n",
    "        if m//q % 2:\n",
    "            return m//p % 2\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        while p%2==0 and q%2==0:\n",
    "            p>>=1\n",
    "            q>>=1\n",
    "        if p%2==0: return 2\n",
    "        if q%2==0: return 0\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        g = gcd(p, q)\n",
    "        l = p * q // g\n",
    "        q = l // q\n",
    "        p = l // p\n",
    "        if p % 2 == 0:\n",
    "            return 0\n",
    "        elif q % 2 == 0:\n",
    "            return 2\n",
    "        else: \n",
    "            return 1\n",
    "\n",
    "        # p //= g\n",
    "        # q //= g\n",
    "        # if p % 2 == 0:\n",
    "        #     return 2\n",
    "        # elif q % 2 == 0:\n",
    "        #     return 0\n",
    "        # else: \n",
    "        #     return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        g = gcd(p, q)\n",
    "        # q走的最少距离\n",
    "        lcm = p * q / g\n",
    "        # 上下走的次数\n",
    "        tb = lcm / p % 2\n",
    "        # 左右走的次数\n",
    "        lr = (lcm * p / q) / p % 2\n",
    "\n",
    "        if tb and lr:\n",
    "            return 1\n",
    "        elif tb:\n",
    "            return 2\n",
    "        elif lr:\n",
    "            return 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def mirrorReflection(self, p, q):\n",
    "        from fractions import Fraction as F\n",
    "\n",
    "        x = y = 0\n",
    "        rx, ry = p, q\n",
    "        targets = [(p, 0), (p, p), (0, p)]\n",
    "\n",
    "        while (x, y) not in targets:\n",
    "            #Want smallest t so that some x + rx, y + ry is 0 or p\n",
    "            #x + rxt = 0, then t = -x/rx etc.\n",
    "            t = float('inf')\n",
    "            for v in [F(-x,rx), F(-y,ry), F(p-x,rx), F(p-y,ry)]:\n",
    "                if v > 0: t = min(t, v)\n",
    "\n",
    "            x += rx * t\n",
    "            y += ry * t\n",
    "\n",
    "            #update rx, ry\n",
    "            if x == p or x == 0: # bounced from east/west wall, so reflect on y axis\n",
    "                rx *= -1\n",
    "            if y == p or y == 0:\n",
    "                ry *= -1\n",
    "\n",
    "        return 1 if x==y==p else 0 if x==p else 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        # def gcd(a, b):\n",
    "        #     if b == 0:\n",
    "        #         return a \n",
    "        #     if a < b:\n",
    "        #         return gcd(b, a)\n",
    "        #     return gcd(b, a%b)\n",
    "        \n",
    "        # g = gcd(p, q)\n",
    "        # k = p // g\n",
    "        # if k % 2 == 0:\n",
    "        #     return 2\n",
    "        # m = k * q // p\n",
    "        # if m % 2 == 0:\n",
    "        #     return 0 \n",
    "        # return 1\n",
    "\n",
    "        # ------------------------------\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a \n",
    "            if a < b:\n",
    "                return gcd(b, a)\n",
    "            return gcd(b, a%b)\n",
    "        \n",
    "        def lcm(a, b):\n",
    "            return a*b // gcd(a, b)\n",
    "        \n",
    "        l = lcm(p, q)\n",
    "        x, y = l//p, l//q\n",
    "        if y % 2 == 0:\n",
    "            return 2\n",
    "        if x % 2 == 0:\n",
    "            return 0 \n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\r\n",
    "\r\n",
    "        # 难道是暴力搜索？？？ \r\n",
    "        # 只有 1000 * 4 个点 ，，，，\r\n",
    "        \r\n",
    "        # 终点是 (0, p), (1, 0), (1, p)\r\n",
    "        k = p // gcd(p, q)\r\n",
    "        if k & 1 == 0:\r\n",
    "            return 2 \r\n",
    "        return k * q // p & 1\r\n",
    "            \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        # 最大公约数\n",
    "        g = gcd(p,q)\n",
    "        # p//g 就代表 p,q的最小公倍数L//p:x\n",
    "        # q//g 就代表 p,q的最小公倍数L//q:y\n",
    "        # x为偶数，一定为2\n",
    "        # x为奇数，为(1,0)，y为奇为1，y为偶为0\n",
    "        x = (p//g)%2\n",
    "        y = (q//g)%2\n",
    "        # x为奇数;y为奇为1\n",
    "        if x and y:\n",
    "            return 1\n",
    "        # x为奇数；y为偶为0\n",
    "        elif x:\n",
    "            return 0\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        k = gcd(p,q)\n",
    "        p = p//k\n",
    "        q = q//k\n",
    "        if p % 2 == 0:\n",
    "            return 2\n",
    "        else:\n",
    "            if q % 2 == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        g  = gcd(p, q)\n",
    "        p = (p / g) % 2\n",
    "        q = (q / g) % 2\n",
    "        if p and q:\n",
    "            return 1\n",
    "        elif p:\n",
    "            return 0\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(p, q):\n",
    "            if q:\n",
    "                return gcd(q, p%q)\n",
    "            return p\n",
    "        n = gcd(p, q)\n",
    "        p, q = p // n, q // n\n",
    "\n",
    "        return (q % 2) * (2 - p % 2)\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        g = gcd(p, q)\n",
    "        move_q = p * q / g\n",
    "        move_p = p * q / g * p / q\n",
    "        k_q = q / g % 2\n",
    "        k_p = p / g % 2\n",
    "\n",
    "        if k_p and k_q:\n",
    "            return 1\n",
    "        elif k_p:\n",
    "            return 0\n",
    "        elif k_q:\n",
    "            return 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        g = gcd(p, q)\n",
    "        p //= g\n",
    "        p %= 2\n",
    "        q //= g\n",
    "        q %= 2\n",
    "        if p == 1 and q == 1:\n",
    "            return 1\n",
    "        elif p == 1:\n",
    "            return 0\n",
    "        else: \n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        cidx = {(p,0):0, (p,p):1, (0,p): 2}\n",
    "\n",
    "        dx, dy = p, q\n",
    "        x, y = 0, 0\n",
    "\n",
    "        while cidx.get((x,y), None) is None:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            \n",
    "            dx = -dx\n",
    "            if y > p:\n",
    "                y = 2*p - y\n",
    "                dy = -dy\n",
    "            if y < 0:\n",
    "                y = -y\n",
    "                dy = -dy\n",
    "            \n",
    "        return cidx[(x,y)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        g = gcd(p, q)\n",
    "        p //= g\n",
    "        q //= g\n",
    "        if p % 2 == 0:\n",
    "            return 2\n",
    "        elif q % 2 == 0:\n",
    "            return 0\n",
    "        else: \n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\r\n",
    "        g=math.gcd(p,q)\r\n",
    "        # v=p*q//g\r\n",
    "        w=(p//g)%2\r\n",
    "        h=(q//g)%2\r\n",
    "        # if w%2:\r\n",
    "        #     if h%2:\r\n",
    "        #         return 1\r\n",
    "        #     else:\r\n",
    "        #         return 0\r\n",
    "        # else:\r\n",
    "        #     if h%2:\r\n",
    "        #         return 2\r\n",
    "        #     else:\r\n",
    "        #         return 0\r\n",
    "        if w and h:\r\n",
    "            return 1\r\n",
    "        elif h:\r\n",
    "            return 2\r\n",
    "        else:\r\n",
    "            return 0\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        while ((p&1)==0 and (q&1)==0):\n",
    "            p>>=1\n",
    "            q>>=1\n",
    "        if (p&1)==0:\n",
    "            return 2\n",
    "        if (q&1)==0:\n",
    "            return 0\n",
    "        return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        g = math.gcd(p, q)\n",
    "        if p//g % 2:\n",
    "            return q//g % 2\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def mirrorReflection(self, p: int, q: int) -> int:\n",
    "#         n=1\n",
    "#         if (p//q)%2==1:\n",
    "#             return 1\n",
    "#         while 1:\n",
    "#             if (n+1)*q==n*p:\n",
    "#                 flag=n+1\n",
    "#                 break\n",
    "#             elif (n+1)*q<n*p:\n",
    "#                 break\n",
    "#             n+=1\n",
    "#         if flag%2==0:\n",
    "#             return 2\n",
    "#         elif flag%2==1:\n",
    "#             return 0\n",
    "class Solution(object):\n",
    "    def mirrorReflection(self, p, q):\n",
    "        def gcd(x, y):           \n",
    "            # 获取最小值\n",
    "            if x > y:\n",
    "                smaller = y\n",
    "            else:\n",
    "                smaller = x           \n",
    "            for i in range(1,smaller + 1):\n",
    "                if((x % i == 0) and (y % i == 0)):\n",
    "                    hcf = i            \n",
    "            return hcf\n",
    "        yue=gcd(p,q)\n",
    "        p=p//yue\n",
    "        q=q//yue\n",
    "        if q%2==0:\n",
    "            return 0\n",
    "        if (p-q)%2==0:\n",
    "            return 1\n",
    "        return 2\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(l,r):return gcd(r%l,l) if r%l else l\n",
    "        return (lambda x:q//x&1 if p//x&1 else 2)(gcd(q,p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        f=Fraction(q,p)\n",
    "        match (f.numerator%2,f.denominator%2):\n",
    "            case (1,1):\n",
    "                return 1\n",
    "            case (1,0):\n",
    "                return 2\n",
    "            case (0,1):\n",
    "                return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        from fractions import Fraction as F\n",
    "\n",
    "        x = y = 0\n",
    "        rx, ry = p, q\n",
    "        targets = [(p, 0), (p, p), (0, p)]\n",
    "\n",
    "        while (x, y) not in targets:\n",
    "            #Want smallest t so that some x + rx, y + ry is 0 or p\n",
    "            #x + rxt = 0, then t = -x/rx etc.\n",
    "            t = float('inf')\n",
    "            for v in [F(-x,rx), F(-y,ry), F(p-x,rx), F(p-y,ry)]:\n",
    "                if v > 0: t = min(t, v)\n",
    "\n",
    "            x += rx * t\n",
    "            y += ry * t\n",
    "\n",
    "            #update rx, ry\n",
    "            if x == p or x == 0: # bounced from east/west wall, so reflect on y axis\n",
    "                rx *= -1\n",
    "            if y == p or y == 0:\n",
    "                ry *= -1\n",
    "\n",
    "        return 1 if x==y==p else 0 if x==p else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        if p % q == 0:\n",
    "            if (p//q) % 2 == 0:\n",
    "                return 2\n",
    "            else:\n",
    "                return 1\n",
    "        else:\n",
    "            #上下方向，1是上，2是下\n",
    "            d1 = 2\n",
    "            #左右方向，奇数是右，偶数是左\n",
    "            d2 = 0\n",
    "            y = 0\n",
    "            while 1:\n",
    "                if (p-y) % q == 0:\n",
    "                    break\n",
    "                a = (p-y)//q\n",
    "                y = q - (p-y)%q\n",
    "                if d1 == 1:\n",
    "                    d1 = 2\n",
    "                else:\n",
    "                    d1 = 1\n",
    "                d2 += a+1\n",
    "\n",
    "            d2 += (p-y)//q\n",
    "            if d1 == 1:\n",
    "                d1 = 2\n",
    "            else:\n",
    "                d1 = 1\n",
    "                \n",
    "            if d2 % 2 == 0:\n",
    "                return 2\n",
    "            elif d1 == 2:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        t = lcm(p,q)\n",
    "        x,y = t//p,t//q\n",
    "        if y & 1: return x&1\n",
    "        else: return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        g = gcd(p,q)\n",
    "        p = (p / g) % 2\n",
    "        q = (q / g) % 2\n",
    "        return 1 if p and q else 0 if p else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        from fractions import Fraction as F\n",
    "\n",
    "        x = y = 0\n",
    "        rx, ry = p, q\n",
    "        targets = [(p, 0), (p, p), (0, p)]\n",
    "\n",
    "        while (x, y) not in targets:\n",
    "            t = float('inf')#表示无穷\n",
    "            for v in [F(-x,rx), F(-y,ry), F(p-x,rx), F(p-y,ry)]:\n",
    "                if v > 0: t = min(t, v)\n",
    "\n",
    "            x += rx * t\n",
    "            y += ry * t\n",
    "\n",
    "            if x == p or x == 0:\n",
    "                rx *= -1\n",
    "            if y == p or y == 0:\n",
    "                ry *= -1\n",
    "\n",
    "        return 1 if x==y==p else 0 if x==p else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(p, q):\n",
    "            if q:\n",
    "                return gcd(q, p%q)\n",
    "            return p\n",
    "        n = gcd(p, q)\n",
    "        p, q = p // n, q // n\n",
    "\n",
    "        return (q % 2) * (2 - p % 2)\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        m = math.lcm(p, q)\n",
    "        if m//q % 2:\n",
    "            return m//p % 2\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        # pq最小公倍数 s = p*q//gcd(p,q)\n",
    "        # k*q = s\n",
    "        g = gcd(p,q)\n",
    "        # 水平方向走了多少个p\n",
    "        m = (q // g) & 1\n",
    "        # 竖直走了多少个q\n",
    "        n = (p // g) & 1\n",
    "        \n",
    "        if m and n:\n",
    "            return 1 # 1个p，1个q\n",
    "        if m == 1 and n == 0:\n",
    "            return 2\n",
    "        if m == 0:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        t = 0\n",
    "        while True:\n",
    "            t += 1\n",
    "            if (p * p * t) % (q * q) == 0:\n",
    "                b = (p * p * t) // (q * q) \n",
    "                if t % 2 == 1:\n",
    "                    if b % 2 == 0:\n",
    "                        return 2\n",
    "                    else:\n",
    "                        return 1\n",
    "                else:\n",
    "                    if b % 2 == 1:\n",
    "                        return 0\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        while p%2==0 and q%2==0:\n",
    "            p>>=1\n",
    "            q>>=1\n",
    "        if p%2==0: return 2\n",
    "        if q%2==0: return 0\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=858 lang=python\n",
    "#\n",
    "# [858] 镜面反射\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def mirrorReflection(self, p, q):\n",
    "        \"\"\"\n",
    "        :type p: int\n",
    "        :type q: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def lcm(x, y):\n",
    "            from math import gcd\n",
    "            return x * y // gcd(x, y)\n",
    "        \n",
    "        lcm_pq = lcm(p, q)\n",
    "        if (lcm_pq//p) % 2 == 0:\n",
    "            return 0\n",
    "        if (lcm_pq//q) % 2 == 0:\n",
    "            return 2\n",
    "        else:\n",
    "            return 1\n",
    "\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        # pq最小公倍数 s = p*q//gcd(p,q)\n",
    "        # k*q = s\n",
    "        g = gcd(p,q)\n",
    "        # 水平方向走了多少个p\n",
    "        m = (q // g) & 1\n",
    "        # 竖直走了多少个q\n",
    "        n = (p // g) & 1\n",
    "        \n",
    "        if m and n:\n",
    "            return 1 # 1个p，1个q\n",
    "        if m == 1:\n",
    "            return 2\n",
    "        if m == 0:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def mirrorReflection(self, p, q):\n",
    "        g = gcd(p, q)\n",
    "        p = (p / g) % 2\n",
    "        q = (q / g) % 2\n",
    "\n",
    "        return 1 if p and q else 0 if p else 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        # 不可能射入0的\n",
    "        # 求p、q的最小公倍数\n",
    "        # mp == nq\n",
    "        # 第一层，第二层，找个规律\n",
    "        a1 = p\n",
    "        b1 = q\n",
    "        while b1:\n",
    "            a1,b1 = b1, a1 % b1\t\t#a1为最大公约数\n",
    "        lca = p * q // a1\n",
    "        n = lca // p-1 \n",
    "        m = lca // q-1 \n",
    "        # print(n,m)\n",
    "        # (0,n)的右上角是2，反之则为1\n",
    "        if m % 2 != 0:\n",
    "            if n % 2 != 0:\n",
    "                return 0 \n",
    "            else:\n",
    "                return 2 \n",
    "        else:\n",
    "            if n % 2 != 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        a = math.gcd(p,q)\n",
    "        p,q = p//a, q//a\n",
    "        if p%2==0: return 2\n",
    "        if q%2==0: return 0\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        # if p%q != 0:\n",
    "        #     return 0\n",
    "        # elif p%q ==0 and (p//q)%2 == 0:\n",
    "        #     return 2\n",
    "        # else:\n",
    "        #     return 1\n",
    "        while q &1 == 0 and p &1 ==0:\n",
    "            q >>=1\n",
    "            p >>=1\n",
    "        if p&1 ==0:\n",
    "            return 2\n",
    "        if q&1 ==0:\n",
    "            return 0\n",
    "        return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\r\n",
    "        g=math.gcd(p,q)\r\n",
    "        v=p*q//g\r\n",
    "        w=v//q\r\n",
    "        h=v//p\r\n",
    "        if w%2:\r\n",
    "            if h%2:\r\n",
    "                return 1\r\n",
    "            else:\r\n",
    "                return 0\r\n",
    "        else:\r\n",
    "            if h%2:\r\n",
    "                return 2\r\n",
    "            else:\r\n",
    "                return 0\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a \n",
    "            if a < b:\n",
    "                return gcd(b, a)\n",
    "            return gcd(b, a%b)\n",
    "        \n",
    "        g = gcd(p, q)\n",
    "        k = p // g\n",
    "        if k % 2 == 0:\n",
    "            return 2\n",
    "        m = k * q // p\n",
    "        if m % 2 == 0:\n",
    "            return 0 \n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        g = gcd(p, q)\n",
    "        p //= g\n",
    "        q //= g\n",
    "        if q % 2 == 0:\n",
    "            return 0\n",
    "        if p % 2 == 0:\n",
    "            return 2\n",
    "        else:\n",
    "            return 1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        # g 最大公约数 \n",
    "        g = gcd(p,q)\n",
    "        x = (p//g)%2\n",
    "        y = (q//g)%2\n",
    "        if x and y:\n",
    "            return 1\n",
    "        elif x:\n",
    "            return 0\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        g = math.gcd(p, q)\n",
    "        # 上下与左右移动次数满足 yq = xp\n",
    "        y = p // g\n",
    "        x = q // g\n",
    "        # 左右移动\n",
    "        if y % 2 == 0:\n",
    "            return 2\n",
    "        # 上下移动\n",
    "        return x % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if a < b: return gcd(b, a)\n",
    "            if a % b == 0: return b\n",
    "            return gcd(b, a % b)\n",
    "        val = gcd(p, q)\n",
    "        np, nq = q // val, p // val\n",
    "        if nq % 2 == 0: return 2\n",
    "        if np % 2 == 1: return 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def mirrorReflection(self, p: int, q: int) -> int:\r\n",
    "\r\n",
    "        # 难道是暴力搜索？？？ \r\n",
    "        # 只有 1000 * 4 个点 ，，，，每个点两种方向\r\n",
    "        \"\"\"\r\n",
    "        终点有   (0, p, 1)\r\n",
    "                (1, 0, -1)\r\n",
    "                (1, p, 1)\r\n",
    "        \"\"\"\r\n",
    "        mp = { \r\n",
    "            (0, p, 1) : 2,\r\n",
    "            (1, 0, -1): 0,\r\n",
    "            (1, p, 1) :1}\r\n",
    "        st = (0, 0, 1)\r\n",
    "        while st not in mp:\r\n",
    "            a = st[0] ^ 1 \r\n",
    "            b = st[1] + st[2] * q \r\n",
    "            c = st[2]\r\n",
    "            if b > p:\r\n",
    "                b = p - (b - p)\r\n",
    "                c = -c\r\n",
    "            elif b < 0:\r\n",
    "                c = -c \r\n",
    "                b = -b \r\n",
    "            st = (a, b, c)\r\n",
    "        return mp[st]\r\n",
    "    \r\n",
    "\r\n",
    "        \r\n",
    "        # k = p // gcd(p, q)\r\n",
    "        # if k & 1 == 0:\r\n",
    "        #     return 2 \r\n",
    "        # return k * q // p & 1\r\n",
    "            \r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
